//给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 
//
// 两棵树重复是指它们具有相同的结构以及相同的结点值。 
//
// 示例 1： 
//
//         1
//       / \
//      2   3
//     /   / \
//    4   2   4
//       /
//      4
// 
//
// 下面是两个重复的子树： 
//
//       2
//     /
//    4
// 
//
// 和 
//
//     4
// 
//
// 因此，你需要以列表的形式返回上述重复子树的根结点。 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 323 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var dist map[string]int
var res []*TreeNode
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	dist = make(map[string]int)
	res = make([]*TreeNode, 0)

	// 每个对比子树的根节点需要做什么？
	// 需要知道自己的整棵树 长什么样子。 然后对比的时候用map，因为不能重复 所以map记录出现次数
	// 知道自己长啥样 后续遍历

	subTree(root)

	return res
}

func subTree(root *TreeNode) string {
	if root == nil {
		return "#"
	}

	left := subTree(root.Left)
	right := subTree(root.Right)

	// 这里注意分隔符！ 不然会出现21 和 2 和 1的冲突
	desc := left + "," + right + "," + strconv.Itoa(root.Val) // 描述子树长的样子

	dist[desc]++

	if dist[desc] == 2 {
		res = append(res, root)
	}

	return desc
}
//leetcode submit region end(Prohibit modification and deletion)
